import java.util.ArrayList;
import java.util.List;

//字母大小写全排列
//测试链接：https://leetcode.cn/problems/letter-case-permutation/
public class LetterCasePermutation {
    List<String> ans;
    public List<String> letterCasePermutation(String s) {
        ans = new ArrayList<>();
        char[] arr = s.toCharArray();

        dfs(arr, 0);
        return ans;
    }

    public void dfs(char[] s, int pos) {
        if(pos == s.length) {
            ans.add(new String(s));
            return;
        }

        if(s[pos] >= '0' && s[pos] <= '9') {  //为数字
            dfs(s,pos+1); //去下一层
            return;
        }

        char c = s[pos];
        dfs(s, pos+1);  //不改变大小写

        if(c >= 'A' && c <= 'Z') {
            s[pos] = (char)(c + 32); //大写变小写
            dfs(s,pos+1);
            s[pos] = c;  //恢复现场
        } else {
            s[pos] = (char)(c -32);
            dfs(s, pos+1);
            s[pos] = c;  //恢复现场
        }
    }
}
